#include "priority_queue.h"
#include <stdlib.h>

typedef struct tnode *Treeptr;

struct tnode {
	element_t       data;
	Treeptr         left;
	Treeptr         right;
};

struct queue_data {
	Treeptr         root;
	Treeptr         min;
	Treeptr         max;
	unsigned int    size;
};

Treeptr         insert(Treeptr p, element_t data, queue target_queue);
void            delete_tree(Treeptr p);



queue 
create(void)
{
	queue           ptr;
	ptr = malloc(sizeof(struct queue_data));

	if (ptr == NULL)
		return NULL;

	ptr->root = NULL;
	ptr->size = 0;
	ptr->min = NULL;
	ptr->max = NULL;

	return ptr;
}


void 
clear(queue target_queue)
{
	delete_tree(target_queue->root);
	target_queue->root = NULL;
	target_queue->size = 0;
	target_queue->min = NULL;
	target_queue->max = NULL;
}



void 
delete(queue target_queue)
{
	delete_tree(target_queue->root);
	free(target_queue);
}



unsigned int 
size(queue target_queue)
{
	return (target_queue->size);
}

bool 
push(queue target_queue, element_t data)
{
	target_queue->root = insert(target_queue->root, data, target_queue);

	if (target_queue->root == NULL)
		return false;

	target_queue->size++;
	return true;
}


bool 
pop(queue target_queue)
{
	Treeptr         temp, temp1, prev;

	if (target_queue->size == 0)
		return false;
	temp = target_queue->root;

	while (temp != target_queue->max) {
		prev = temp;
		temp = temp->left;
	}

	temp1 = target_queue->max;

	if (target_queue->max->right == NULL) {
		//Î±ÎœÎ¿Î¶Î·ÏÎ¿ÏÎŒÎµÎœÎ¿ÏÎŽÎµÎœÎµÏÎµÎ¹Î±Î»Î»Î¿ÎºÎ¿ÎŒÎ²Î¿Îœ
			target_queue->max = prev;
		//ÎºÎ±ÎœÏmax Î ±ÏÏÎ¿ÎœÏ119Î¿ÏÎŽÎµÎ¹ÏÎœÎµÎ¹ÏÎµÎ±ÏÏÎ¿
			prev->left = NULL;
		free(temp1);
	} else {
		//Î±ÎœÎ¿Î¶Î·ÏÎ¿ÏÎŒÎµÎœÎ¿ÏÎµÏÎµÎ¹ÎºÎ¿ÎŒÎ²Î¿
			target_queue->max = target_queue->max->right;
		//ÎºÎ±ÎœÏmax Ï Î¿ÎŽÎµÎŸÎ¹Ï119Î±Î¹ÎŽÎ¹ÏÎ¿Ï
			prev->left = temp1->right;
		//ÎºÎ±ÎœÏÏÎ¿ÎœÏ119ÏÎ¿Î·Î³Î¿ÏÎŒÎµÎœÎ¿ÎºÎ¿ÎŒÎ²Î¿ÎœÎ±ÎŽÎµÎ¹ÏÎœÎµÎ¹ÏÏÎ¿ÎŽÎµÎŸÎ¹Ï119Î±Î¹ÎŽÎ¹ÏÎ¿ÏÎ¶Î·ÏÎ¿ÏÎŒÎµÎœÎ¿Ï
			free(temp1);
	}

	target_queue->size--;
	return true;
}

bool 
front(queue target_queue, element_t * data)
{
	if (size(target_queue) == 0)
		return false;

	*data = target_queue->max->data;
	return true;
}



bool 
back(queue target_queue, element_t * data)
{
	if (size(target_queue) == 0)
		return false;

	*data = target_queue->min->data;
	return true;
}

Treeptr 
insert(Treeptr p, element_t data, queue target_queue)
{
	if (p == NULL) {
		p = malloc(sizeof(struct tnode));

		if (p == NULL)
			return NULL;
		p->data = data;
		p->left = NULL;
		p->right = NULL;

		if (target_queue->size == 0) {
			target_queue->min = p;
			target_queue->max = p;
		} else if (data > target_queue->max->data)
			target_queue->max = p;
		else if (data < target_queue->min->data)
			target_queue->min = p;
	} else if (data > p->data)
		p->left = insert(p->left, data, target_queue);
	else
		p->right = insert(p->right, data, target_queue);

	return p;
}

void 
delete_tree(Treeptr p)
{
	if (p == NULL)
		return;

	delete_tree(p->left);
	delete_tree(p->right);
	free(p);
}
